Modern society and technology are increasingly based on digital electronic devices. Personal computers (PCs), digital versatile disk (DVD) players and recorders, and set top boxes for digital cable systems are among the numerous examples of such devices. Many digital electronic devices include multiple autonomous or semi-autonomous functional modules, such as processors, that share access to common resources, such as memory.
FIG. 1 shows the functional modules and their interconnections within one example of a digital electronic device that has multiple functional modules, each of which independently access a shared or common system resource. Digital system 100 includes two requesters 110, which are functional modules that make requests on responder 140 which includes main memory 144. System 100 also includes bus network 130 that conveys requests 120 from the requesters to the responder, and conveys responses 125 from the responder back to the corresponding requestor.
Requestor 110A is a programmed microprocessor and requestor 110B is a special-purpose processor, specifically a video encoder/decoder. Requestors 110 generate requests 120 for main memory 144, which is a common resource within system 100. The requestors provide these requests to bus network 130. Requestors 110 are able to communicate among each other via interrupts 150, as well as by passing information back and forth by encoding it as data that is held in main memory 144.
Bus network 130 includes one or more buses that convey information as electronic signals among devices. Requests 120, which include data and addresses, and responses 125 which include data, addresses and status information, are transferred between two functional modules via bus network 130. The bus network may be a single bus, or may include relay circuitry that transfers information across multiple buses.
Bus network 130 receives a request 120 from either requester 110A or requester 110B, and then delivers the request to responder 140. Bus network also receives responses 125 from requester 140 and provides the responses to either requestor 110A or 110B, according to addressing information contained within each response.
Responder 140 includes main memory 144 and memory controller 142. Memory controller 142 receives access requests from each of requestors 110 via bus network 130, resolves any contentions that occur when more than one access request is active at the same time, determines an order in which the access requests are to be performed, and presents one access request at a time to main memory 144.
Main memory 144 is a random access memory (RAM). Each access request includes the address or address range within the RAM that is to be read or written. Write access requests also include the data that is to be written. When main memory 144 performs a write access request, memory controller 142 generates a write status response and provides it to bus network 130 as an occurrence of response 125 that is addressed to the requestor that generated the write request. When main memory 144 performs a read access request, the memory recalls the data stored at the specified address or addresses and provides that data to controller 142, which in turn includes the data in one or more occurrences of response 125, each of which is addressed to the requestor that generated the read request.
For multimedia systems, as well as for other digital devices where data communication can be a performance bottleneck, the features provided by the bus network that links the requestors to the responders can have a substantial impact on overall system performance. One example of a bus network design that advantageously increases system performance is a bus that includes multiple parallel channels that support simultaneous transfer of request, response, data, address and status data, or of some combination thereof.
Such a multi-channel bus must be designed to operate according to a bus network protocol. Each requestor in such a system must be designed to operate according to the protocol, as must each controller within a responder. Most bus network protocols rely on a transaction ordering policy. Typically a transaction ordering policy defines:                The order in which multiple access requests are performed; and        How an access request is synchronized or connected together with the response resulting from that request.        
An access request and its associated response together comprise a complete transaction, but they occur at separate times, that is, during separate bus cycles. The different channels within a bus may at the same time carry both the response to an earlier access request and a new access request.
A first example of a transaction ordering policy is a global first-in-first-out (FIFO) policy. Under this policy, each transaction is completed, and the completion is indicated via a response being generated from the responder, before the responder performs any other access request. This policy provides the necessary definition of the performance order of multiple access requests. This policy also defines an advantageously simple mechanism to associate requests with the corresponding responses.
A second example of a transaction ordering policy is a first-in-first-out (FIFO) policy among transactions from the same requester along with a free-flowing, unconstrained order among transactions from different requesters. This ordering policy requires that a requestor identifier (ID) signal be associated with channel within each bus. Access requests with the same requestor ID value are performed first in first out, while transactions with different IDs are unordered and may be performed in any order. The value of the requestor ID is provided by the responder in the response, and is used by the requesters to associate the request with its corresponding response.
A third example of a transaction ordering policy is one that places no constraints on when transactions are performed, either within transactions from a single requestor or among transactions from multiple requesters.
FIFO ordering can negatively impact performance. This is especially the case in systems characterized by multiple data streams that have large differences in the data rates of the streams. This situation is common in multimedia systems, where video data streams have data rates that are substantially higher than high-fidelity audio data streams, which in turn have substantially higher data rates than conversational audio data streams. In a multimedia system, operating under either the first or the second example of a FIFO transaction ordering policy, higher rate data streams can easily become blocked waiting for lower rate data streams to complete transactions.
On the other hand, unordered transactions can cause errors to occur in those transactions where correct operation of the system requires access requests to be performed in a particular order. To eliminate these potential errors, the requestors using unordered transactions must impose transaction ordering in those situations in which performance order is important.
FIG. 2 illustrates how an example of two transactions flows through bus network 130. Information flow 200 is illustrated as a matrix, in which each row represents a functional module within the system. Each column of the matrix represents a bus cycle. During any particular bus cycle, at most one value is transferred on each channel of each bus within the bus network. Each cell of the matrix contains a description of the information that flows during the corresponding bus cycle to the corresponding functional module from the bus network, or to the bus network from that functional module.
In this example, responder 140 does not order transactions among different requestors. To compensate for this, when ordering is important the two requesters must operate together to impose the proper order of performing the transactions. Thus, information flow 200 applies both to systems that follow either the second example transaction ordering policy in which transactions from the same requestor are given a FIFO order, and to systems that follow the third example transaction ordering policy in which the bus network imposes no order on any transactions.
Information flow 200 shows the information going into and out of the bus network during a period of 16 bus cycles. This period starts with when the access request for the first transaction is generated and ends with when the response to the second transaction is received.
The first transaction is a read request from requestor 110A, the second transaction is a write request from requestor 110B. This example assumes that proper system operation occurs only when the data read from the responder is the value of the data prior to the write, which case occurs when the requestors are using system memory to pass information from requestor 110B to requestor 110A.
In bus cycle 1, requestor 110A generates read access request 220 and provides it to the bus network. The bus network may be pipelined to allow shorter bus cycles, may include multiple buses with relay circuitry among the buses, or may contain a FIFO register to interface between buses operating at different bus cycle rates. In such bus networks, information requires some number of clock cycles to move through the bus network. In the example of FIG. 2, the latency of the bus network is assumed to be two bus cycles. Thus after two cycles, i.e., in cycle 3, responder 140 receives read request 220.
In the example of FIG. 2, responder 140 is assumed to not be busy with any other transactions and to be able, when not busy, to respond to a request in the bus cycle after the request is received. Thus in cycle 4, the responder generates response to read request 222A and provides it to the bus network. In the example of FIG. 2, the read request is assumed to be for a short block of contiguous data that requires 4 bus cycles to be transferred. Thus in cycles 5, 6 and 7, the responder generates responses to read request 222B, 222C and 222D. Each response 222 includes providing to the bus network a portion of the data being held in responder 140 that was requested by requestor 110A.
Responses to read request 222 are received by requester 110A during cycles 6 through 9. Because the bus network of this example imposes no ordering on access requests from different requesters, the responsibility of ensuring that the first transaction is performed prior to the second transaction falls on the requesters. To ensure this transaction order, in bus cycle 10 requestor 110A generates notification 224 that the read transaction is complete and provides the notification to requestor 110B.
In the example of FIG. 2, it is assumed that requestor 110A is capable of generating notification 224 in the bus cycle immediately after receiving the final read response 222D, that requester 110B is able to receive the notification in the same bus cycle without any latency, and that requestor 110B is able to generate write request 226 without any latency in the bus cycle immediately after receiving notification.
In cycle 13, responder 140 receives write request 226 from the bus network. In cycle 14, responder 140 performs the write request, generates write status response 228, and provides it to the bus network. In cycle 16, requester 110B receives write status response 228. Thus, the two example transactions of information flow 200 of FIG. 2 are completed in 16 bus cycles.
The assumptions used in information flow 200 may be optimistic. There could easily be a latency of six to twelve cycles (compared to two cycles in flow 200) between the bus cycle in which the final read response 222D is received (cycle 9 in flow 200) and the bus cycle in which write request 226 is generated (cycle 11 in flow 200). There could easily be a latency of six to twelve cycles (compared to two cycles in flow 200) for requests and responses to pass through bus network 130.
Thus, the performance of digital system 100 for the transaction example can be summarized in Table 1, which gives the bus cycles required for bus latencies of two, six and twelve cycles and for inter-requestor latencies of two, six and twelve cycles.
TABLE 1Bus cyclesrequired fortransactionBusBusBusexampleLatency = 2Latency = 6Latency = 12Inter-requestor163256Latency = 2Inter-requestor203660Latency = 6Inter-requestor264266Latency = 12